\section{Related Work} \label{sec:related-work}


\subsection{Computational generation of referring expressions}


The generation of referring expressions is a well developed field in automated natural language generation.
Building upon GRE foundational work~\cite{winograd,dale89cooking,Dale1995},
various proposals have investigated the generation of different kinds of referring expressions 
such as relational expressions (``the blue ball next to the cube''~\cite{dale91:_gener_refer_expres_invol_relat}),
reference to sets (``the two small cubes''~\cite{Stone2000}), or more expressive logical connectives (``the 
blue ball not on top of the cube''~\cite{deemter02:_gener_refer_expres}).

The idea of using a formal language to describe the information that an RE should convey has been discussed 
in~\cite{Krahmer2003,gardent07:_gener_bridg_defin_descr}.  In~\cite{arec2:2008:Areces,arec:usin11} the 
combination of partition refinement algorithms and different formal languages is used to classify existing 
GRE approaches in an expressiveness hierarchy.  For instance, the classical Dale and Reiter algorithms
compute purely conjunctive formulas; \cite{deemter02:_gener_refer_expres} extends this language by
adding the other propositional connectives, whereas~\cite{dale91:_gener_refer_expres_invol_relat} extends it by
allowing existential quantification.


\subsection{Cognitive models for the generation of referring expressions}



